package 算法.leetcode.offer.base;

import java.util.*;

/**
 * @author lchenglong
 * @date 2022/3/18
 */
public class TreeNode {

    public int val;

    public TreeNode left;

    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(2);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(4);
        list.add(3);

        TreeNode root = init(list);
        TreeNode.print(root);
    }

    public static TreeNode init2(String str){
        String[] split = str.split(",");
        List<Integer> list = new ArrayList<Integer>();
        for (String s : split){
            list.add(s.equals("null")?null:Integer.parseInt(s));
        }
        return init(list);
    }
    public static TreeNode init(List<Integer> array){
        List<TreeNode> ans = new ArrayList<TreeNode>(array.size());
        for (int i=0;i<array.size();i++){
            ans.add(null);
        }
        for (int i=0;i<array.size();i++){
            TreeNode node= ans.get(i);
            if (null == node ){
                if (null != array.get(i)) {
                    node = new TreeNode(array.get(i));
                    ans.set(i,node);
                }
            }
            if (node !=null) {
                if (2 * i + 1 < array.size()) {
                    if (null != array.get(2 * i + 1)) {
                        TreeNode left = new TreeNode(array.get(2 * i + 1));
                        node.left = left;
                        ans.set(2 * i + 1, left);
                    }
                }
                if (2 * i + 2 < array.size()) {
                    if (null != array.get(2 * i + 2)) {
                        TreeNode left = new TreeNode(array.get(2 * i + 2));
                        node.right = left;
                        ans.set(2 * i + 2,left);
                    }
                }
            }
        }
        return ans.get(0);
    }

    public static void  print(TreeNode root){
        List<List<Integer>> ans = levelOrder(root);
        for (List<Integer> list:ans){
            System.out.print(Arrays.toString(list.toArray()));
            System.out.println();
        }
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List list= new ArrayList();
        if(root==null){
            return list;
        }
        // 使用队列先进先出的特点来存储每层节点的值
        Queue<TreeNode> queue= new LinkedList();
        queue.add(root);
        while(true){
            List<Integer> levelList=new ArrayList();
            int size= queue.size();
            if(size==0){
                return list;
            }
            // 遍历队列取出上层所有的数据
            for(int i=0;i<size;i++){
                TreeNode t=queue.poll();
                levelList.add(t.val);
                if(t.left!=null){
                    queue.add(t.left);
                }
                if(t.right!=null){
                    queue.add(t.right);
                }
            }
            list.add(levelList);
        }

    }
}
